package com.ctwom.algorithm.questions.Hfind;

/**
 * 用二分查找查询有序数组中大于某个数最左
 * eg：1，2，3，3，3，4，5，5，6，7， 大于3的最左元素是第5位的4元素
 */
public class GreaterThanItemLeftEstFind {
    public static void main(String[] args) {
        int[] arr = {0, 1, 1, 2, 3, 3, 4, 5, 5, 7, 8, 88, 345};
        System.out.println(greaterThanItemLeftEstFind(arr, 5));
    }

    public static int greaterThanItemLeftEstFind(int[] arr, int num) {
        int start = 0;
        int end = arr.length;
        int n = arr.length;

        //不断循环缩小开始和结束区域直到只有自己1个元素，来找到元素
        while (n >= 1) {
            n = (end - start) / 2;
            //主要是二分完的元素和所查找元素相同时，向左看还是向右看，
            //向左看是end控制结尾始终是我们想要的值，所以就会一直找到第一个然后-1就是想要的小于某个值最右；
            //向右看是start控制开始始终是我们想要的值，所以就会一直找到最后一个然后+1就是想要的大于某个值最左；
            if (arr[start + n] > num) {
                end = start + n;
            } else {
                start = start + n;
            }
        }
        if (arr[start] == num) {
            if (start + 1 < arr.length) {
                return arr[start + 1];
            }
        }
        return -1;
    }
}
